/**
 * 生成一组模拟数据
 * 从 0，0 位置开始  到 500，500 ， 两点之间间隔 10
 */
let interval = 15;
let baseCoordinate = []; // 基础坐标
let coordinateMap = {}; // 基础坐标的map结构（方便后续查询节点）
let unPassMap = {}; // 不可通过的坐标
let rangeX = [0, 60];
let rangeY = [0, 60];
let isPass = true;
for (let x = rangeX[0]; x < rangeX[1]; x++) {
  for (let y = rangeY[0]; y < rangeY[1]; y++) {
    isPass = Math.random() > 0.2 ? true : false;
    let node = {
      type: "rect",
      x: x * interval,
      y: y * interval,
      id: `${x * interval}${y * interval}`,
      width: interval,
      height: interval,
      fillType: isPass ? "stroke" : "fill",
      fillColor: "#1E90FF",
      unClick: !isPass,
      isPass,
    };
    baseCoordinate.push(node);
    if (!isPass) {
      unPassMap[node.id] = { x: x * interval, y: y * interval };
    }
    coordinateMap[node.id] = node;
  }
}

/**
 * 根据 起点 、 终点 计算路径，并返回路径坐标数组
 */
function findRoute(start, end) {
  let usedRouteMap = {}; // { 节点id: true }  被使用过的节点
  let unUsedRoutes = []; // [{ id: 节点id, length: 理想距离, x, y }]  未被使用的节点

  let startNode = getListNode(start.x, start.y); // 记录链表结构，开始节点为第一个
  usedRouteMap[start.id] = true;

  /**
   * 获取下一个节点（一直获取到终点为止）
   * @param {*} sNode 当前节点（当前进行寻路的节点）
   * @param {*} pNode 父级节点（上一个节点）
   * @returns
   */
  const getNextNode = (sNode) => {
    // 1、获取当前节点上下左右四个方向的坐标信息
    // let around = [
    // 	{ x: sNode.x, y: sNode.y - interval }, // 上
    // 	{ x: sNode.x, y: sNode.y + interval }, // 下
    // 	{ x: sNode.x - interval, y: sNode.y }, // 左
    // 	{ x: sNode.x + interval, y: sNode.y }, // 右
    // ];
    let around = [];
    let t = { x: sNode.x, y: sNode.y - interval }; // 上
    let b = { x: sNode.x, y: sNode.y + interval }; // 下
    let l = { x: sNode.x - interval, y: sNode.y }; // 左
    let r = { x: sNode.x + interval, y: sNode.y }; // 右
    /**
     * 判断节点位置，根据节点位置调整搜索策略
     * 例如，节点 a 在节点 b 的右上角，如果  a 到 b 上，y 的差值大于 x 的差值（a.y - b.y > a.x - b.x ），则优先在 y 上移动
     */
    if (end.x > sNode.x) {
      // 终点在起点右侧
      if (Math.abs(end.y - sNode.y) > Math.abs(end.x - sNode.x)) {
        // y 上的距离 > x 上的距离   先找 y，再找 x
        if (end.y > sNode.y) {
          around = [b, r, t, l];
        } else {
          around = [t, r, b, l];
        }
      } else {
        // x 上的距离 > y 上的距离   先找 x，再找 y
        if (end.y > sNode.y) {
          around = [r, t, b, l];
        } else {
          around = [r, b, t, l];
        }
      }
    } else {
      // 终点在起点左侧
      if (Math.abs(end.y - sNode.y) > Math.abs(end.x - sNode.x)) {
        if (end.y > sNode.y) {
          // y 上的距离 > x 上的距离   先找 y，再找 x
          around = [b, l, t, r];
        } else {
          around = [t, l, b, r];
        }
      } else {
        // x 上的距离 > y 上的距离   先找 x，再找 y
        if (end.y > sNode.y) {
          around = [l, t, b, r];
        } else {
          around = [l, b, t, r];
        }
      }
    }

    // 2、判断这四个坐标是否为有效坐标，满足以下三个条件：  可通过 && 在网格范围内 && 该坐标没有被使用过 ， 并记录下满足条件的坐标
    let passLength = [];
    around.forEach((p) => {
      let nodeId = `${p.x}${p.y}`;
      if (
        coordinateMap[nodeId] &&
        coordinateMap[nodeId].isPass &&
        !usedRouteMap[nodeId]
      )
        passLength.push(p);
    });

    // 2、将这些节点插入进链表，并根据其大小值排序
    let lengthSort = [];
    for (let n of passLength) {
      let node = getListNode(n.x, n.y);
      let length = getPathLength(n, end);
      node.parent = sNode;
      node.length = length;
      lengthSort.push({
        length,
        node,
      });
      // 3、记录下当前未使用的节点（当进行下一次循环的时候，需要在这些节点中寻找一个离终点最近的节点作为开头）
      unUsedRoutes.push(node);
      // 4、验证是否为终点，如果为终点，则直接返回当前节点，终止查询
      if (n.x === end.x && n.y === end.y) {
        // console.log('到终点了', n.x, n.y);
        // endNode = node;
        return node;
      }
    }
    lengthSort
      .sort((a, b) => a.length - b.length)
      .forEach((n, i) => {
        sNode[`next${i + 1}`] = n; // 根据距离排序，依次插入链表上一个节点中
      });

    // 5、统计未被使用的节点，找到最小的节点，重复 1、2 步骤
    if (unUsedRoutes.length) {
      unUsedRoutes = unUsedRoutes.sort((a, b) => a.length - b.length);
      let minLengthNode = unUsedRoutes[0];
      // unUsedRoutes = unUsedRoutes.slice(1, unUsedRoutes.length);
      unUsedRoutes.shift();
      usedRouteMap[minLengthNode.id] = true;
      return getNextNode(minLengthNode);
    }
  };

  // 获取整个路径的最后一个节点
  let lastNode = getNextNode(startNode);
  // 5、处理这个节点，获取完整的结构
  let result = [];
  const getPath = (node) => {
    result.push(node.id);
    if (node.parent) {
      getPath(node.parent);
    }
  };
  if (lastNode) getPath(lastNode);
  console.timeEnd("findRoute");
  return { result, usedRouteMap, unUsedRoutes };
}

/**
 * 获取节点队列
 */
class ListNode {
  constructor(x, y) {
    this.parent = null; // 当前节点的上一级
    this.length = 0; // 当前节点距终点的理想长度
    this.id = `${x}${y}`; // 当前节点的 id
    this.x = x;
    this.y = y;
    this.next1 = null; // 可能的节点（一个节点下最多有三个节点供使用）
    this.next2 = null;
    this.next3 = null;
  }
}
function getListNode(x, y) {
  return new ListNode(x, y);
}

/**
 * 计算开始到结束坐标的理想距离
 * 理想距离指 不考虑碰撞的情况下开始点到结束点最短的距离 ，计算方式为(end.x - start.x) + (end.y - start.y)
 * @param {x: number, y: number} start
 * @param {x: number, y: number} end
 */
function getPathLength(start, end) {
  return Math.abs(end.x - start.x) + Math.abs(end.y - start.y);
}

export { baseCoordinate, findRoute };
